#include <iostream>
#include <map>
#include <string>

/**
 * @brief 查找cname链的开头位置
 *
 */
template<typename K, typename V>
K findStartCname(const std::map<K, V>& mapping) {
    // 创建逆向映射
    std::map<V, K> reverseMapping;
    for (const auto& pair : mapping) {
        reverseMapping[pair.second] = pair.first;
    }

    // 从每个键向前查找，直到遇到没有前驱的键
    for (const auto& pair : mapping) {
        if (reverseMapping.find(pair.first) == reverseMapping.end()) {
            return pair.first;
        }
    }

    return {}; // 如果没有找到开始键，则返回一个空值
}

int main() {
    std::map<std::string, std::string> mapping = {
        {"value2", "value3"},
        {"a", "b"},
        {"b", "c"},
        {"c", "d"},
        {"d", "e"},
        {"e", "key1"},
        {"key1", "value1"},
        {"value1", "value2"},
    };

    std::string startKey = findStartCname(mapping);
    std::cout << "The start key of the map chain is \"" << startKey << "\"." << std::endl;

    return 0;
}
